package top100;

import java.util.concurrent.ForkJoinPool;

/**
 * @author Godc
 * @description
 */
public class LongestPalindrome {
    public static void main(String[] args) {
        LongestPalindromeSolution s = new LongestPalindromeSolution();
        String a = s.longestPalindrome1("ababa");
        System.out.println(a);
    }
}
class LongestPalindromeSolution {
    /**
     * 中心扩散，枚举中心点,时间o(n^2)，空间o(1)
     * @param s
     * @return
     */
    int maxLeft,maxRight,max = -1;
    public String longestPalindrome(String s) {
        for (int i = 0; i < s.length(); i++) {
            reverseString(s,i,i);
            reverseString(s,i,i+1);
        }
        return s.substring(maxLeft,maxRight+1);
    }
    public void reverseString(String s,int i,int j){
        while(i>=0&&j<s.length()&&s.charAt(i)==s.charAt(j)){
            if(j-i+1>max){
                maxLeft = i;
                maxRight = j;
                max = j-i+1;
            }
                i--;
                j++;
        }
    }

    /**
     * DP，时间复杂度o(n^2),空间o(n^2)，并不是最优解
     * @param s
     * @return
     */
    public String longestPalindrome1(String s){
        int max = -1;
        int len = s.length();
        int left = 0,right = 0;
        // dp定义:dp[i][j]的子串是否是回文子串
        int[][] dp = new int [len][len];
        // 递推公式:dp[i][j] = dp[i+1][j-1]^si==sj
        // 初始化:数组初始化为0，未匹配
        // 遍历顺序：i，j和i+1于j-1有关，所以从下往上，从左往右遍历
        for (int i = s.length()-1; i >=0 ; i--) {
            for (int j = i; j < s.length(); j++) {
                if(s.charAt(i)==s.charAt(j)){
                    // 如果子串1位回文，如果两位，并且s.charAt(i)==s.charAt(j)说明也回文
                    if(j-i<=1||dp[i+1][j-1]==1) dp[i][j]=1;
                }
                if(dp[i][j]==1&&j-i+1>max){
                    max = j-i+1;
                    left = i;
                    right = j;
                }
            }
        }
        return s.substring(left,right+1);
    }

}